/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-21 18:48:57
 * @LastEditors: lily
 * @LastEditTime: 2021-04-21 19:51:10
 */
/*
 * @lc app=leetcode.cn id=53 lang=javascript
 *
 * [53] 最大子序和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */

//  思路：贪心
//  看当前子序列和是否有增益效果（>0）
//  复杂度：O(n)、O(1)

var maxSubArray = function (nums) {
    // 当前最大连续子序列和为 sum
    let sum = 0, max = nums[0]
    for (let num of nums) {
        // 当前sum对结果无增益效果，需舍弃
        if (sum < 0) {
            // sum 更新为当前遍历数字
            sum = num
        } else {
            // 有增益效果，加上后续数字
            sum += num
        }
        max = Math.max(sum, max)
    }
    return max
};
// @lc code=end

console.log(maxSubArray([1]));